package simple

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
// 整个数组往后移动后的数组
// 一开始还考虑步长是否会被数组长度整除的情况，但是要得到公约数，非常不方便
// 最终解法: 先反转整个数组，然后再分别反转前半部分和后半部分
func getNextIndex(currentIndex, step, len int) int {
	if currentIndex+step >= len {
		return step - (len - currentIndex)
	}
	return currentIndex + step
}

func Rotate(nums []int, step int) {
	for step >= len(nums) {
		step -= len(nums)
	}
	if step <= 0 {
		return
	}
	start, end := 0, len(nums)-1
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}

	start, end = 0, step-1
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}

	start, end = step, len(nums)-1
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start++
		end--
	}
}
